use std::ptr;

struct Queue {
    head: Option<Box<Node>>,
    tail: Option<*mut Node>,
}

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

impl Queue {
    fn new() -> Self {
        Queue { head: None, tail: None }
    }

    fn push_head(&mut self, value: i32) {
        let mut new_node = Box::new(Node { value, next: self.head.take() });
        self.head = Some(new_node);
        if self.tail.is_none() {
            self.tail = self.head.as_mut().map(|node| &mut **node as *mut Node);
        }
    }

    fn pop_head(&mut self) -> Option<i32> {
        self.head.take().map(|node| {
            self.head = node.next;
            if self.head.is_none() {
                self.tail = None;
            }
            node.value
        })
    }

    fn peek_head(&self) -> Option<&i32> {
        self.head.as_ref().map(|node| &node.value)
    }

    fn push_tail(&mut self, value: i32) {
        let mut new_node = Box::new(Node { value, next: None });
        if let Some(tail) = self.tail.take() {
            unsafe {
                (*tail).next = Some(new_node);
            }
        } else {
            self.head = Some(new_node);
        }
        self.tail = Some(&mut **self.head.as_mut().unwrap() as *mut Node);
    }

    fn pop_tail(&mut self) -> Option<i32> {
        if self.head.is_none() {
            return None;
        }
        let mut current = &mut self.head;
        while let Some(ref mut next_node) = current.as_mut().unwrap().next {
            current = &mut next_node.next;
        }
        let value = current.take().map(|node| node.value);
        if self.tail == current {
            self.tail = None;
        }
        value
    }

    fn peek_tail(&self) -> Option<&i32> {
        self.tail.map(|tail| unsafe { &(*tail).value })
    }

    fn is_empty(&self) -> bool {
        self.head.is_none()
    }
}

fn run_tests() {
    let mut queue = Queue::new();

    // test_queue_new_free
    assert!(queue.is_empty());

    // test_queue_push_head
    queue.push_head(1);
    assert_eq!(queue.peek_head(), Some(&1));
    queue.push_head(2);
    assert_eq!(queue.peek_head(), Some(&2));

    // test_queue_pop_head
    assert_eq!(queue.pop_head(), Some(2));
    assert_eq!(queue.pop_head(), Some(1));
    assert_eq!(queue.pop_head(), None);

    // test_queue_peek_head
    queue.push_head(3);
    assert_eq!(queue.peek_head(), Some(&3));
    queue.pop_head();
    assert_eq!(queue.peek_head(), None);

    // test_queue_push_tail
    queue.push_tail(4);
    assert_eq!(queue.peek_tail(), Some(&4));
    queue.push_tail(5);
    assert_eq!(queue.peek_tail(), Some(&5));

    // test_queue_pop_tail
    assert_eq!(queue.pop_tail(), Some(5));
    assert_eq!(queue.pop_tail(), Some(4));
    assert_eq!(queue.pop_tail(), None);

    // test_queue_peek_tail
    queue.push_tail(6);
    assert_eq!(queue.peek_tail(), Some(&6));
    queue.pop_tail();
    assert_eq!(queue.peek_tail(), None);

    // test_queue_is_empty
    assert!(queue.is_empty());
    queue.push_head(7);
    assert!(!queue.is_empty());
    queue.pop_head();
    assert!(queue.is_empty());

    println!("All tests passed!");
}

fn main() {
    run_tests();
}
